#include <stdio.h>
#include <stdlib.h>

typedef char        ElementType;
typedef struct TNode*Position;
typedef Position    BinTree;
struct TNode
{
    ElementType Data;
    BinTree     Left;
    BinTree     Right;
};

BinTree CreatBinTree()
{return NULL;} /* 实现细节忽略 */
void InorderTraversal(BinTree BT);

void PreorderTraversal(BinTree BT);

void PostorderTraversal(BinTree BT);

void LevelorderTraversal(BinTree BT);

int main()
{
    BinTree BT=CreatBinTree();
    printf("Inorder:");
    InorderTraversal(BT);
    printf("\n");
    printf("Preorder:");
    PreorderTraversal(BT);
    printf("\n");
    printf("Postorder:");
    PostorderTraversal(BT);
    printf("\n");
    printf("Levelorder:");
    LevelorderTraversal(BT);
    printf("\n");
    return 0;
}

/* 你的代码将被嵌在这里 */
void print(BinTree BT)
{
    printf(" %c",BT->Data);
}

void InorderTraversal(BinTree BT)
{
    if(BT)
    {
        InorderTraversal(BT->Left);
        print(BT);
        InorderTraversal(BT->Right);
    }
}

void PreorderTraversal(BinTree BT)
{
    if(BT)
    {
        print(BT);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
}

void PostorderTraversal(BinTree BT)
{
    if(BT)
    {
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        print(BT);
    }
}

BinTree                queue[100000];
int                 head=0,tail=0;

void push(BinTree node)
{
    if(node)
        queue[tail++]=node;
}

int empty(void)
{
    return head==tail;
}

BinTree pop(void)
{
    return queue[head++];
}

void LevelorderTraversal(BinTree BT)
{
    push(BT);
    while(!empty())
    {
        BinTree t=pop();
        push(t->Left);
        push(t->Right);
        print(t);
    }
}
